package 力扣;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: a
 * Date: 2022-10-03
 * Time: 10:47
 */
public class surrounded_regions {
    private static int[] getX = {0, 1, 0, -1};
    private static int[] getY = {1, 0, -1, 0};

    private static void DFS(char[][] board, int[][] book, int row, int col, int x, int y){
        book[x][y] = 1;
        for(int i = 0; i < 4; i++){
            int newx = x + getX[i];
            int newy = y + getY[i];
            if(newx >= 0 && newx < row && newy >= 0 && newy < col && board[newx][newy] == 'O' && book[newx][newy] == 0){
                DFS(board, book, row, col, newx, newy);
            }
        }
    }

    public static void solve(char[][] board) {
        int row = board.length;
        int col = board[0].length;
        if(row <= 2){
            return;
        }
        int[][] book = new int[row][col];
        //在四条边上寻找字符'O'
        for(int i = 0; i < row; i++){
            if(board[i][0] == 'O'){
                DFS(board, book, row, col, i, 0);
            }
            if(board[i][col - 1] == 'O'){
                DFS(board, book, row, col, i, col - 1);
            }
        }
        for(int i = 0; i < col; i++){
            if(board[0][i] == 'O'){
                DFS(board, book, row, col, 0, i);
            }
            if(board[row - 1][i] == 'O'){
                DFS(board, book, row, col, row - 1, i);
            }
        }
        //更新整个矩阵
        for(int i = 0; i < row; i++){
            for(int j = 0; j < col; j++){
                if(board[i][j] == 'O' && book[i][j] == 0){
                    board[i][j] = 'X';
                }
            }
        }
    }

    public static void main(String[] args) {
        char[][] board = {{'O','X','O'},{'X','O','X'},{'O','X','O'}};
        solve(board);
    }
}
